package middle;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.LinkedBlockingDeque;

public class Solution_547 {
    public int findCircleNum(int[][] isConnected) {
        UnionFind unionFind = new UnionFind(isConnected.length);
        for (int i = 0; i < isConnected.length; i++) {
            int[] ints = isConnected[i];
            for (int j = 0; j < ints.length; j++) {
                if (ints[j] == 1) {
                    unionFind.union(i, j);
                }
            }
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < isConnected.length; i++) {
            int root = unionFind.find(i);
            set.add(root);
        }
        return set.size();
    }

    static class UnionFind {
        private final int[] parent;

        public UnionFind(int size) {
            parent = new int[size];
            for (int i = 0; i < parent.length; i++) {
                parent[i] = i;
            }
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                parent[rootI] = rootJ;
            }
        }

        private int find(int i) {
            if (i != parent[i]) {
                parent[i] = find(parent[i]);
            }
            return parent[i];
        }
    }


    public int findCircleNum1(int[][] isConnected) {
        int[] provinces = new int[isConnected.length];
        Arrays.fill(provinces, -1);
        Queue<Integer> queue = new LinkedBlockingDeque<>();
        for (int i = 0; i < isConnected.length; i++) {
            if (provinces[i] < 0) {
                queue.add(i);
                while (!queue.isEmpty()) {
                    Integer index = queue.poll();
                    provinces[index] = i;
                    for (int j = 0; j < isConnected[index].length; j++) {
                        if (isConnected[index][j] == 1 && provinces[j] < 0) {
                            queue.add(j);
                        }
                    }
                }
            }
        }
        Set<Integer> set = new HashSet<>();
        for (int province : provinces) {
            if (province >= 0) {
                set.add(province);
            }
        }
        return set.size();
    }

    public static void main(String[] args) {
        Solution_547 model = new Solution_547();
        System.out.println(model.findCircleNum(new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}));
        System.out.println(model.findCircleNum(new int[][]{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}));
        System.out.println(model.findCircleNum(new int[][]{{1, 0, 0, 1}, {0, 1, 1, 0}, {0, 1, 1, 1}, {1, 0, 1, 1}}));
        System.out.println("-----");
        System.out.println(model.findCircleNum1(new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}));
        System.out.println(model.findCircleNum1(new int[][]{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}));
        System.out.println(model.findCircleNum1(new int[][]{{1, 0, 0, 1}, {0, 1, 1, 0}, {0, 1, 1, 1}, {1, 0, 1, 1}}));
    }
}
